#include <iostream>
#include <queue>



void
merge(int *s, int low, int mid, int high)
{
  std::queue<int> buf1;
  std::queue<int> buf2;
  int i;

  for (i = low; i <= mid; ++i)
    {
      buf1.push(s[i]);
    }

  for (i = mid+1; i <= high; ++i)
    {
      buf2.push(s[i]);
    }

  i = low;
  while (!buf1.empty() && !buf2.empty())
    {
      if (buf1.front() < buf2.front())
	{
	  s[i++] = buf1.front();
	  buf1.pop();
	}
      else
	{
	  s[i++] = buf2.front();
	  buf2.pop();
	}
    }

  while (!buf1.empty())
    {
      s[i++] = buf1.front();
      buf1.pop();
    }

  while (!buf2.empty())
    {
      s[i++] = buf2.front();
      buf2.pop();
    }
}



void
merge_sort(int* s, int low, int high)
{
  if (low < high)
    {
      int mid = (low + high) / 2;
      merge_sort(s, low, mid);
      merge_sort(s, mid+1, high);
      merge(s, low, mid, high);
    }
}



int main(int argc, char* argv[])
{
  int n;

  if (argc == 1)
    {
      n = 10;
    }
  else
    {
      n = atoi(argv[1]);
    }

  srand ( time(NULL) );
  
  std::cerr << "Original array:" << std::endl;
  int s[n];
  int i;

  for (i = 0; i < n; ++i)
    {
      s[i] = rand() % 100;
      std::cerr << s[i] << " ";
    }
  std::cerr << std::endl;

  merge_sort(s, 0, n-1);

  std::cerr << "Sorted array:" << std::endl;
  for (i = 0; i < n; ++i)
    {
      std::cerr << s[i] << " ";
    }
  std::cerr << std::endl;
}
